package algorithmExample.Heap;

import lombok.Data;

import java.util.Arrays;
import java.util.List;
import java.util.Objects;
import java.util.stream.Collectors;

/**
 * @Author: zhangrongqing
 * @Date: 2019/11/13 18:40
 */

//合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
//
//        示例:
//
//        输入:
//        [
//          1->4->5,
//          1->3->4,
//          2->6
//        ]
//        输出: 1->1->2->3->4->4->5->6

public class MergeKSortedLists {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) {
            return null;
        }
        int minNode = 0;
        boolean needInitial = true;
        ListNode result = null;
        ListNode start = null;
        while (true) {
            int count = 0;
            int minValue = Integer.MAX_VALUE;
            for (int i = 0; i < lists.length; i++) {
                if (lists[i] == null) {
                    count++;
                    continue;
                }
                if (lists[i].val < minValue) {
                    minValue = lists[i].val;
                    minNode = i;
                }
            }
            if (count == lists.length) {
                return start;
            }
            if (needInitial) {
                result = new ListNode(minValue);
                start = result;
                needInitial = false;
            } else {
                ListNode nextListNode = new ListNode(minValue);
                result.next = nextListNode;
                result = nextListNode;
            }
            if (lists[minNode] != null) {
                lists[minNode] = lists[minNode].next;
            }

        }
    }


    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(1);
        listNode1.next = new ListNode(4);
        listNode1.next.next = new ListNode(5);

        ListNode listNode2 = new ListNode(1);
        listNode2.next = new ListNode(3);
        listNode2.next.next = new ListNode(4);

        ListNode listNode3 = new ListNode(2);
        listNode3.next = new ListNode(6);

        ListNode result = new MergeKSortedLists().mergeKLists(new ListNode[]{listNode1, listNode2, listNode3});
        System.out.println("result:" + result);
    }
}

//@Data
class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}